题解 P5876@洛谷 【化简单词】

看来前面题解的各种做法(其实也就两种),我决定给你们写一篇STL的。

介绍一下使用的函数:substr()

这个函数有两个参数,第一个是起始位置,第二个是子串长度,作用是取字符串的一部分,返回值为这段的内容。用法:

string s;
s.substr(0, 5);

表示取字符串 ss 的前五位。

看一眼数据范围

发现可以暴力!于是就有了下面的思路:

枚举每个字符串,枚举前缀位数,判断这个前缀是否也是其他字符串的前缀:如果是,前缀位数加一,继续判断;如果不是,说明找到了最短的前缀,输出。

你们最爱的代码

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin>>n;
	string s[51];
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=s[i].length();j++)
		{
			bool book = true;
			for(int k=1;k<=n;k++)
			{
				if(k == i) continue;
				if(s[i].substr(0, j) == s[k].substr(0, j))
				{
					book = false;
					break;
				}
			}
			if(book)
			{
				cout<<s[i].substr(0, j)<<endl;
				break;
			}
		}
	}
	return 0;
}

实测AC。